Hardness results for maximum agreement problems have close connections to hardness results for proper learning in computational learning theory. In this paper we prove two hardness results for the problem of finding a low degree polynomial threshold function (PTF) which has the maximum possible agreement with a given set of labeled examples in Rn x {-1; 1}.
展开▼
机译：最大一致性问题的硬度结果与在计算机学习理论中正确学习的硬度结果紧密相关。在本文中，我们针对发现低阶多项式阈值函数（PTF）的问题证明了两个硬度结果，该函数与给定的一组标记示例Rn x {-1;具有最大可能的一致性。 1}。
展开▼
